In order to solve the problem of low partition accuracy of measurement set and high computational complexity, a Gaussian-mixture hypothesis density intensity multi-extended target tracking algorithm based on improved K-means++ clustering algorithm was proposed. Firstly, the traversal range of K value was narrowed according to the situations that the targets may change at the next moment. Secondly, the predicted states of targets were used to select the initial clustering centers, providing a basis for the correct partition of measurement set to improve the accuracy of clustering algorithm. Finally, the proposed improved K-means++ clustering algorithm was applied to the Gaussian-mixture probability hypothesis filter to jointly estimate the number and states of multiple targets. The simulation results show that the average tracking time of the proposed algorithm is reduced by 59.16% and 53.25% respectively, compared with that of multi-extended target tracking algorithms based on distance partition and K-means++. Meanwhile, the Optimal Sub-Pattern Assignment (OSPA) of the proposed algorithm is much lower than that of above two algorithms. In summary, the algorithm can greatly reduce the computational complexity and achieve better tracking performance than existing measurement set partition methods.